package com.mononite.ac

class AhoCorasick {
	private root

	AhoCorasick(words) {
		buildTrie(words)
		buildLinks()
	}

	private buildTrie(words) {
		root = [:]
		words.findAll { it.size() > 0 }.each { addWord(it) }
		
		if (!root) {
			throw new IllegalArgumentException('Invalid words: ' + words)
		}
	}

	private addWord(word) {
		def node = root
		word.each { ch ->
			node[(ch)] = node[(ch)] ?: [:] 
			node = node[(ch)] 
		}
		node.accept = word	
	}

	private buildLinks() {
		def nodes = [root] as Queue, node
		while (node = nodes.poll()) {
			node.findAll { it.key.size() == 1 }.each { ch, child ->
				nodes.offer(child)

				child.fail = nextByFailLinks(node, ch)
				child.dict = child.fail.accept ? child.fail : child.fail.dict
			}
		}
	}

	private nextByFailLinks(node, ch) {
		def fail = node.fail
		while (fail) {
			if (fail[(ch)]) {
				return fail[(ch)]
			}
			fail = fail.fail
		}
		return root
	}

	def matches(text) {
		def results = [], current = root
		text.eachWithIndex { ch, index ->
			current = current[(ch)] ?: nextByFailLinks(current, ch)
			acceptCurrentMatched(results, current, index)
		}
		return results
	}

	private acceptCurrentMatched(results, current, index) {
		current.accept && results << makeResult(current, index) 

		def node = current
		while (node = node.dict) {
			results << makeResult(node, index)
		}
	}

	private makeResult(node, index) {
		def start = index - node.accept.size() + 1
		return [start : start, word : node.accept]
	}
}

